/**
 * Created with IntelliJ IDEA
 * Description:单向 非顺序 无头结点
 * User:恋恋
 * Date:2022-11-01
 * Time:16:53
 */
public class MySingleList {

    //静态内部类或者普通内部类

    static class MyList{

        public int val;

        //引用类型默认为null
        public MyList next;

        public MyList(int val) {

            this.val = val;

        }
    }

    //头结点
    public MyList head;

    public void Creation(){
        MyList myList1=new MyList(1);
        MyList myList2=new MyList(1);
        MyList myList3=new MyList(1);
        MyList myList4=new MyList(1);
        MyList myList5=new MyList(1);
        MyList myList6=new MyList(1);

        //串起来
        myList1.next=myList2;
        myList2.next=myList3;
        myList3.next=myList4;
        myList4.next=myList5;
        myList5.next=myList6;
        //设置头节点
        this.head=myList1;

    }
    public void display(){
        MyList cur=this.head;

//这里也包含了单链表为空的情况
        while(cur!=null){

            System.out.print(cur.val+" ");

            cur=cur.next;

        }
        System.out.println();
    }
    public void display(MyList list){
        MyList cur=list;

//这里也包含了单链表为空的情况
        while(cur!=null){

            System.out.print(cur.val+" ");

            cur=cur.next;

        }
        System.out.println();
    }
    //头插法

    public void addFirst(int data){

        MyList cur=new MyList(data);

        //单链表为空
        if(this.head==null){
            this.head=cur;
            return;
        }
        //单链表不为空
            cur.next=this.head;
            this.head=cur;


    }

    //尾插法

    public void addLast(int data){
        MyList newList=new MyList(data);


        //单链表为空
        if(this.head==null){
            this.head=newList;
            return;
        }

        //单链表不为空
        //首先找到最后一个结点
        MyList cur=this.head;
        while(cur.next!=null){

            cur=cur.next;

        }
        //此时cur指向最后一个结点
        cur.next=newList;

    }

    //任意位置插入,第一个数据节点为0号下标

    public boolean addIndex(int index,int data) throws IndexException{
        //任意位置添加
        //这里需要考虑下标是否合法
        if(index<0 || index>this.size()){

            throw new IndexException("下标越界！");

        }
        //考虑插入的下标是尾巴还是头部

        if(index==0){

            this.addFirst(data);
            return true;
        }
        if(index==this.size()){

            this.addLast(data);
            return true;
        }
//插入到中间的位置
        MyList newList=new MyList(data);
        MyList cur=FindIndexList(index);
        newList.next=cur.next;
        cur.next=newList;
        return true;

    }
    // 找到下标为index前面的MyList
    public MyList FindIndexList(int index){

        //让cur先走index-1步

        MyList cur=this.head;

        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        //返回index前一个结点
        return cur;
    }

    //查找是否包含关键字key是否在单链表当中

    public boolean contains(int key){
        MyList cur=this.head;
        while (cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点

    public void remove(int key){
        //判断头节点是否是key
       if(this.head.val==key){

           head=head.next;

       }
        //判断是否包含这个key
       MyList cur= FindBeforeList(key);
        if(FindBeforeList(key)==null){
            System.out.println("单链表中不存在这个"+key);
            return;
        }
        cur.next=cur.next.next;
    }
    public MyList FindBeforeList(int key){
        MyList cur=this.head;

        while(cur.next!=null){
//注意这里不能是cur!=null,因为当cur遍历到最后一个结点时，会发生空指针异常cur.next.val--也说明这个第一个结点是不能被判断的！！！！！

            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    //删除所有值为key的节点

////这个方法的时间复杂度已经到达了O（n^2）
//    public void removeAllKey(int key){
//        MyList cur=this.head;
//        while(cur!=null){
//            remove(key);
//            cur=cur.next;
//        }
//    }
    public void removeAllKey(int key){
/*
第一次写：
 */
//        //删除key在头部的位置,一直删除，将key作为头节点的位置全部删除
//        MyList cur=this.head;
//        while(head.val==key){
//            head=head.next;
//        }
//        //删除Key在里面的位置和尾位置
//        if(this.head!=null){
//            MyList front,back;
//            front=this.head;
//            back=this.head.next;
//            while(back!=null){
//                if(back.val==key){
//                    front.next=back.next;
//                }
//                if(back.val!=key){
//                    front=front.next;
//                }
//
//                back=back.next;

//
//            }
//        }
        System.out.println("===============================================");
//        while(head.val==key){
//            head=head.next;
//        }
        if(this.head==null){
            return;
        }
        MyList cur=this.head.next;
        MyList prev=this.head;

            while(cur!=null){
                if(cur.val==key){
                    prev.next=cur.next;
                    cur=cur.next;
                }else{
                    prev=cur;//   相同   prev=prev.next;
                    cur=cur.next;


                }
            }


        if(this.head.val==key){
            head=head.next;
        }

    }

//
    //得到单链表的长度

    public int size(){

        MyList cur=this.head;
        //计算器
        int count=0;
        //这个已经包含了单链表为空的情况

        while(cur!=null){

            count++;
            cur=cur.next;

        }

        return count;
    }
   public void clear(){
//粗暴的做饭
       this.head=null;
//仔细的做法
       while(head!=null){
           MyList cur=head.next;
           head=null;
           head=cur;
       }
   }
   /*
    反转字符串
    */
   public void reverseList() {
       //判断是否为空链表
       if(this.head==null){
           return;
       }
       //判断是否只有一个元素
       if(this.head.next==null){
           return;
       }
       MyList cur=this.head.next;
       MyList curNext=this.head.next.next;

       cur.next=this.head;
       this.head.next=null;
       this.head=cur;
       while(curNext!=null){
           cur=curNext;
           curNext=curNext.next;
           cur.next=this.head;
          this.head=cur;
       }


   }
    public MyList reverseList(MyList head) {
        //判断是否为空链表
        if(this.head==null){
            return null;
        }
        //判断是否只有一个元素
        if(this.head.next==null){
            return null;
        }
        MyList cur=this.head.next;
        MyList curNext=this.head.next.next;

        cur.next=this.head;
        this.head.next=null;
        this.head=cur;
        while(curNext!=null){
            cur=curNext;
            curNext=curNext.next;
            cur.next=this.head;
            this.head=cur;
        }
        return this.head;

    }
   /*
    给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结
点
    **采用快慢指针！**
    */
    public MyList middleNode(MyList head) {
        MyList fast=this.head;//快指针
        MyList slow =this.head;//慢指针
        //当fast==null，说明这个链表是奇数，当fast.next==null,说明这个链表是偶数的
        //只要有一个条件不符合就不满足
        while(fast.next!=null && fast!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    /*
     输入一个链表，输出该链表中倒数第k个结点。
     */
    public MyList FindKthToTail(MyList head,int k) {
//        if(k<0||k>this.size()){
//            return null;
//        }
        if( k < 0 || head == null ){
            return null;
        }

        MyList fast = this.head;
        MyList slow = this.head;
        while( k-1!= 0 ){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;

    }
}
